/**
 * 给出一个区间的集合，请合并所有重叠的区间。
 * 示例一:
 *  输入: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
 *  输出: [[1, 6], [8, 10], [15, 18]]
 *  解释: 区间[1, 3]和[2, 6]重叠，将他们合并为[1, 6]
 * 示例二:
 *  输入: intervals = [[1, 4], [4, 5]];
 *  输出: [[1, 5]]
 *  解释: 区间[1, 4]和[4, 5]可被视为重叠区间。
*/
function mergeIntervals (intervals) {
    const result = [];
    // 1. 先把区间按开始位置排序
    const sortIntervals = intervals.sort((a, b) => a[0] - b[0])
    // 2. 比较第一个的结束位置和第二个的开始位置，如果第一个的结束位置大于第二个的开始位置，那么合并两个区间
    for (let i = 0; i < sortIntervals.length; i++) {
        if (!result.length) {
            result.push(sortIntervals[i]);
        } else {
            const target = result[result.length - 1];
            // 3. 合并区间的结束位置，第一个结束位置的大就用第一个的结束位置的元素，否则用第二个
            if (target[1] >= sortIntervals[i][0]) {
                target[1] = Math.max(target[1], sortIntervals[i][1]);
            } else {
                result.push(sortIntervals[i]);
            }
        }
    }
    return result;
    
}

console.log(mergeIntervals([[1, 3], [2, 6], [15, 18], [8, 10]]));
console.log(mergeIntervals([[1, 4], [4, 5]]));